#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAXSIZE 100

typedef int Position;
typedef struct LNode *List;
struct LNode {
    int Data[MAXSIZE];
    Position Last;
};

bool Insert(List, int);
Position BinarySearch(List, int, Position, Position);

bool NumberExist = true;
bool *NumberExistPointer = &NumberExist;

int main()
{
    int i = 0, numberToInsert;
    List L;
    L = (List)malloc(sizeof(struct LNode));

    printf("Ints number: ");
    scanf(" %d", &L->Last);
    printf("Input numbers: ");
    while (i < L->Last)
        scanf(" %d", &L->Data[i++]);

    printf("Input the number to insert: ");
    scanf(" %d", &numberToInsert);
    
    // int InsertPosition = BinarySearch(L, numberToInsert, 0, L->Last) + 1;
    // if (InsertPosition > L->Last)
    //     InsertPosition = L->Last;
    // printf("Insert position is %d", InsertPosition);
    if (Insert(L, numberToInsert))
        printf("Insert Success");
    else
        printf("Number already exists\n");
    
    printf("Now the vector is: ");
    for (i = 0; i < L->Last; i++)
        printf("%d ", L->Data[i]);

    return 0;
}

bool Insert(List L, int X)
{
    int InsertPosition = BinarySearch(L, X, 0, L->Last) + 1;
    if (InsertPosition > L->Last)
        InsertPosition = L->Last;

    if (!*NumberExistPointer) {
        for (int i = L->Last; i >= InsertPosition; i--)
            L->Data[i + 1] = L->Data[i];
        L->Data[InsertPosition] = X;
        L->Last = L->Last + 1;
    }
    
    return *NumberExistPointer;
}

Position BinarySearch(List L, int X, Position Left, Position Right)
{
    if (Right < Left) {
        *NumberExistPointer = false;
        return Right;
    }
    
    Position Mid = (Left + Right) / 2;
    if (L->Data[Mid] > X)
        return BinarySearch(L, X, Left, Mid - 1);
    else if (L->Data[Mid] < X)
        return BinarySearch(L, X, Mid + 1, Right);
    else
        return Mid;
}